77C - Beavermuncher-0xFF - CodeForces Solution

#include<bits/stdc++.h>
#define int long long
#define M 100005
using namespace std;
int k[M], a[M];
vector<int> g[M];
int s;

inline void dfs(int u, int f) {
    if (u != s) {
        k[u]--;
        a[u] = 2;
    }
    vector<int> son;
    son.clear();
    int cnt = 0;
    for (int v : g[u]) {
        if (v == f)
            continue;
        dfs(v, u);
        cnt += k[v];
        son.push_back(a[v]);
    }
    sort(son.rbegin(), son.rend());
    for (int i = 0; i < son.size() && k[u]; i++) {
        a[u] += son[i];
        k[u]--;
    }
    a[u] += 2 * min(k[u], cnt);
    k[u] -= min(k[u], cnt);
    return;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> k[i];
    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    cin >> s;
    dfs(s, 0);
    cout << a[s] << endl;
    return 0;
}//1758490611307803121